package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何检测一个较大的单链表是否有环

func main() {
	head := &common.LNode{}
	common.CreateNode4(head, 8)

	meetNode := isLoop(head)
	if meetNode != nil {
		fmt.Println("有环")
		loopNode := findLoopNode(head, meetNode)
		fmt.Println("环的入口点为：", loopNode.Data)
	} else {
		fmt.Println("无环")
	}
}

func isLoop(head *common.LNode) *common.LNode {
	if head == nil || head.Next == nil {
		return head
	}

	slow := head.Next
	fast := head.Next

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return slow
		}
	}

	return nil
}

func findLoopNode(head *common.LNode, meetNode *common.LNode) *common.LNode {
	first := head.Next
	second := meetNode

	for first != second {
		first = first.Next
		second = second.Next
	}

	return first
}
